package one.one.nineteen;

import java.time.LocalDate;

public class Fibonacci {

	static long F(int N) {
		if (N == 0)
			return 0;
		if (N == 1)
			return 1;
		return F(N - 1) + F(N - 2);
	}

	static long FwithArray(int N) {
		if (N == 0)
			return 0;
		if (N == 1)
			return 1;
		long a[] = new long[N];
		a[0] = 0;
		a[1] = 1;
		for (int i = 2; i < N; i++) {
			a[i] = a[i - 1] + a[i - 2];
		}
		return a[N - 1] + a[N - 2];
	}

	public static void main(String[] args) throws Exception {

		int N=50;
		
		long s = System.currentTimeMillis();
		long r = F(N);
		long dF = System.currentTimeMillis() - s;
		System.out.println("F:"+dF);
		
		s = System.currentTimeMillis();
		long rr = FwithArray(N);
		long dFwithArray = System.currentTimeMillis() - s;
		System.out.println("FwithArray:"+dFwithArray);
		
		System.out.println(r);
		System.out.println(rr);
	}

}
